import java.util.HashSet;
import java.util.PriorityQueue;

public class NthUglyNumber {

    public static void main(String[] args) {
        NthUglyNumber nthUglyNumber = new NthUglyNumber();
        System.out.println(nthUglyNumber.nthUglyNumber(19));
    }

    public int nthUglyNumber1(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        HashSet<Long> set = new HashSet<>();
        int[] element = {2, 3, 5};
        set.add(1l);
        heap.add(1l);
        long poll = 0l;
        for (int i = 0; i < n; i++) {
            poll = heap.poll();
            for (int ele : element) {
                long temp = ele * poll;
                if (!set.contains(temp)) {
                    heap.add(temp);
                    set.add(temp);
                }
            }
        }
        return (int) poll;
    }

    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i = 1; i < n; i++) {
            int a = dp[p2] * 2;
            int b = dp[p3] * 3;
            int c = dp[p5] * 5;
            dp[i] = Math.min(a, Math.min(b, c));
            if (a == dp[i]) p2++;
            if (b == dp[i]) p3++;
            if (c == dp[i]) p5++;
        }
        return dp[n - 1];
    }
}
